package j04zuoye;

import java.util.Scanner;

/*
1,找3个数
有一组已经排好顺序的数据：5,13,19,21,37,56,64,75,80,88,92。编写代码
查询数组中是否包含数
查询数组中是否包含数据78，21，13。
使用二分查找法
    int[] arr = {11,33,55,77};


    //偶数 length = 4
    mid = 4/2 = 2

    //奇数
    int[] arr = {11,33,55,77,99};
    //5/2 = 2
    mid = 5/2 = 2

    // [....90,91,92,93,94,95,96,97,98,99,100]
    mid = (min + max)/2
    190/2 = 95

 */
public class J01find2 {
    public static void main(String[] args) {
        //目标数组  5,13  0,1
        int arr[] = {5,13,19,21,37,56,64,75,80,88,92};
        //寻找目标
        int goal = 88;
        // 小下标
        int minPos = 0;
        //最大下标
        int maxPos = arr.length-1;
        //不知道循环次数，while
        while (true){
            int midPos = (minPos + maxPos)/2;
            System.out.println("midPos = " + midPos);
            if(arr[midPos] == goal){
                //找到了
                System.out.println(goal+"找到了，下标为："+midPos);
                break;
            }else if(arr[midPos] > goal){
                //在左边,更新最大下标
                maxPos = midPos - 1;
            }else {
                //在右边
                minPos = midPos + 1;
            }
            //寻找是否结束
            if(minPos>maxPos){
                System.out.println("查找结束，没有："+goal);
                break;
            }
        }

    }
}

class Find2{
    public static void main(String[] args) {
        //目标数组  5,13  0,1
        int[] arr = {5,13,19,21,37,56,64,75,80,88,92};
        //多个目标
        int[] goalArr = {78,21,13};
        for (int i = 0; i < goalArr.length; i++) {
            int goal = goalArr[i];
            int minPos=0,maxPos=arr.length-1;
            //二分查找
            while (true){
                int midPos = (minPos+maxPos)/2;
                if(arr[midPos]==goal){
                    System.out.println(goal+"存在，下标为："+midPos);
                    break;
                }else if(arr[midPos]>goal){
                    maxPos = midPos-1;
                }else {
                    minPos = midPos+1;
                }
                //找不到
                //{1,2}  2
                // (0 + 1)/2 = 0
                //min+1 = 1   max = 1
                if(minPos>maxPos){
                    System.out.println(goal+"不存在");
                    break;
                }
            }
            
        }
    }
}
class Binary{
    public static void main(String[] args) {
        int [] array={5,13,19,21,37,56,64,75,80,88,92};
        int min=0;
        Scanner s=new Scanner(System.in);
        int max= array.length-1;
        System.out.print("请输入你要查询的数字：");
        int findNumber=s.nextInt();
        for (int i = 0; i < array.length; i++) {
            int mid=(min+max)/2;
            if (array[mid]<findNumber)
                min=mid+1;
            if (array[mid]>findNumber)
                max=mid-1;
            if (array[mid]==findNumber){
                System.out.println("数组中有数字："+findNumber);
                break;
            }else{
                System.out.println("数组中没有数字："+findNumber);
                break;
            }
        }
    }
}

class zuoye2 {
    public static void main(String[] args) {
        int[] a={5,13,19,21,37,56,64,75,80,88,92};
        int[] c={78,21,13};
        for (int j = 0; j < c.length; j++) {
            int qian=0;
            int hou=a.length-1;
            int zhong=0;
            int i=0;//找到了几个
            int zhao=c[j];
            boolean b=true;//假如没有
            while (qian<=hou){
                zhong=(hou+qian)/2;
                if (a[zhong]==zhao){
                    i++;
                    b=false;//假如失败，有
                    System.out.println("有"+a[zhong]);
                    break;
                }else if(a[zhong]>zhao){
                    hou=zhong-1;
                    i++;
                }else if(a[zhong]<zhao){
                    qian=zhong+1;
                    i++;
                }
            }
            if (b==true){
                System.out.println("没有"+a[zhong]);
            }
        }
    }
}

class Shiwen{
    public static void main(String[] args) {
        int[] arr = {5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92};
        // 二分查找算法
        int[] targets = {78, 21, 13};
        boolean[] found = new boolean[targets.length];
        for (int i = 0; i < targets.length; i++) {
            int target = targets[i];
            int left = 0;
            int right = arr.length - 1;
            found[i] = false;

            while (left <= right) {
                // 90 +
                // 。。。。。90,91,92,93,94,95,mid
                int temp = left + (right - left) / 2;
                if (arr[temp] == target) {
                    found[i] = true;
                    break;
                } else if (arr[temp] < target) {
                    left = temp + 1;
                } else {
                    right = temp - 1;
                }
            }

        }

        for (int i = 0; i < found.length; i++) {
            if(found[i]==true){
                System.out.println(targets[i]+"有");
            }else{
                System.out.println(targets[i]+"没有");
            }
        }

        /*
        // 输出结果
        if (found[0]) {
            System.out.println("数组中包含78");
        } else {
            System.out.println("数组中不包含78");
        }

        if (found[1]) {
            System.out.println("数组中包含21");
        } else {
            System.out.println("数组中不包含21");
        }

        if (found[2]) {
            System.out.println("数组中包含13");
        } else {
            System.out.println("数组中不包含13");
        }*/
    }
}